Python算法与数据结构 |
您所在的位置：网站首页 › python 列表求最大值 › Python算法与数据结构 |
Python算法与数据结构
|
Python算法与数据结构--求所有子数组的和的最大值
玄魂工作室-玄魂 玄魂工作室秘书 玄魂工作室?昨天 题目：输入一个整形数组，数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。 求所有子数组的和的最大值。要求时间复杂度为O(n)。 这个题目有多个解法，比如可以用一个二维数组存之前每个数据的和，然后在进行大小比较；但是这样时间负责度就是O(n2)了。 换个思路思考下，因为是要最大数，那么就不需要存储，只需要找最大值就可以了。但是为了找子序列的最大和，在遇到相加为负数的情况要跳过，这块注意代码中最后一个if的注释。 基本思路：一个数一个数相加，相加后和最大数以及当前这个数对比，找出最大的；如果相加后是负数，则累加清零 代码----------- # -*- coding: utf-8 -*- """ 题目：输入一个整形数组，数组里有正数也有负数。 数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。 求所有子数组的和的最大值。要求时间复杂度为O(n)。 基本思路：一个数一个数相加，相加后和最大数以及当前这个数对比，找出最大的；如果相加后是负数，则累加清零 """ if __name__ == "__main__": #初始化数组，测试数据 #dataList = [-3,-10,30,-5,-6,-100,300] #dataList = [-3,-10,-30,-5,-6,-1,-100,-300] #dataList = [-3,-10,0,-5,-6,-100,-300] dataList = [3,10,0,5,6,100,300] #dataList = [0,0,0,0,0,0,0] #prd_data用来记录前面累加的数，一旦累加值是负数，则清零 pre_data = dataList[0] #用来记录最大值 max_data = pre_data #遍历数据组进行累加和大小对比 for i in range(len(dataList)): currData = dataList[i] #第一个数用来做初始化，从第二个数开始算 if i==0: continue else: #相加后进行temp_data，max_data以及currData的大小对比，找出最大的 temp_data = currData + pre_data if temp_data > currData: if temp_data > max_data: max_data = temp_data else: if currData > max_data: max_data = currData #如果相加后是负数，则清0，因为一旦出现负数在相加只会让最大值变小 #这块注意**********一定是相加后是负数，而不是这个数本身是负数*********** #因为本身是负数，但是相加后是正数，对后面的数据增大还是有帮助的 if temp_data > 0: pre_data = temp_data else: pre_data = 0 print max_data精品网络安全视频推荐 - 传说的黑麒麟 精品网络安全课推荐--《密码安全攻防技术精讲》 web安全入门课程推荐--Web 安全恩仇录：漏洞原理 欢迎关注玄魂工作室垂直订阅号 “白话算法”。
优质算法课程推荐，扫码了解详情：
Python算法与数据结构--求所有子数组的和的最大值 原文：https://www.cnblogs.com/xuanhun/p/9523568.html |
【本文地址】
今日新闻 |
推荐新闻 |